package com.LeeCode;

import java.util.HashSet;
import java.util.Set;

/**
 * 拆分字符串使唯一子字符串的数目最大
 */

public class Code1593 {
    public static void main(String[] args) {
        String s = "aa";
        System.out.println(new Code1593().maxUniqueSplit(s));
    }

    private int ans = 0;

    public int maxUniqueSplit(String s) {
        backtrace(s, 0, new HashSet<>());
        return ans;
    }


    // 从答案视角，每次选一个
    private void backtrace(String s, int index, Set<String> set) {
        if (index >= s.length()) {
            ans = Math.max(ans, set.size());
            return;
        }

        for (int end = index + 1; end <= s.length(); ++end) {
            String sub = s.substring(index, end);
            if (set.contains(sub)) continue;
            set.add(sub);
            backtrace(s, end, set);
            set.remove(sub);
        }
    }
}
